/*
 * @lc app=leetcode.cn id=204 lang=javascript
 *
 * [204] 计数质数
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    let count=0
    let signs=[]
    for(let i=2;i<n;i++){
        if(!signs[i]){//不是任何数的倍数，count++
            count++
        }
            for(let j=2*i;j<n;j+=i){
                signs[j]=j//利用signs数组接收2的倍数，3的倍数，5的倍数，等等，即去除非质数
            }
        
    }
    return count
};
// @lc code=end
now=new Date()
var countPrimes = function(n) {
    if(n<=2)return 0
    let count=0
    for(let i=2;i<n;i++){
        let flag=true
        for(j=i-1;j>1;j--){
            if(i%j===0){ flag=false ;break}
        }
        if(flag)count++
    }
    return count
};//AC超时
console.log(new Date()-now)
var countPrimes = function(n) {
    let  db=[]
    db[0]=0
    db[1]=0
    let isPrime=function(x){
        if(x<2)return false
        if(x==2)return true
        for(let i=2;i<x;i++){
            if(x%i===0)return false
        }
        return true
    }
    for(let i=2;i<=n;i++){
        db[i]=db[i-1]+isPrime(i-1)
    }
    return db[n]//动态规划还是超时，其中已经优化不少
};